#include <bits/stdc++.h>
using namespace std;

/*
3197. 包含所有 1 的最小矩形面积 II
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形，并且满足 grid 中所有的 1 都在这些矩形的内部。

返回这些矩形面积之和的 最小 可能值。

注意，这些矩形可以相接。

 

示例 1：

输入： grid = [[1,0,1],[1,1,1]]

输出： 5

解释：



位于 (0, 0) 和 (1, 0) 的 1 被一个面积为 2 的矩形覆盖。
位于 (0, 2) 和 (1, 2) 的 1 被一个面积为 2 的矩形覆盖。
位于 (1, 1) 的 1 被一个面积为 1 的矩形覆盖。
示例 2：

输入： grid = [[1,0,1,0],[0,1,0,1]]

输出： 5

解释：



位于 (0, 0) 和 (0, 2) 的 1 被一个面积为 3 的矩形覆盖。
位于 (1, 1) 的 1 被一个面积为 1 的矩形覆盖。
位于 (1, 3) 的 1 被一个面积为 1 的矩形覆盖。
 

提示：

1 <= grid.length, grid[i].length <= 30
grid[i][j] 是 0 或 1。
输入保证 grid 中至少有三个 1 。
*/

// 法一
class Solution {
public:
    int minimumSum(vector<vector<int>>& grid) {
        // 全局矩形边界
        int m = grid.size();
        int n = grid[0].size();

        // 缩小范围 先做点剪枝
        int minR = m, maxR = -1;
        int minC = n, maxC = -1;  // 修正：minC初始值应为n（列数），而非m

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    minR = min(minR, i);
                    maxR = max(maxR, i);
                    minC = min(minC, j);
                    maxC = max(maxC, j);
                }
            }
        }

        // 没有1 直接给0（题目约束下可能到不了这）
        if (maxR == -1) return 0;

        // 结果值的初始化
        int ans = INT_MAX;

        // lambda辅助函数：计算子区域内包含所有1的最小矩形面积
        auto getArea = [&](int r1, int r2, int c1, int c2) {
            int areaMinR = r2, areaMaxR = r1;
            int areaMinC = c2, areaMaxC = c1;
            bool hasOne = false;
            for (int i = r1; i <= r2; i++) {
                for (int j = c1; j <= c2; j++) {
                    if (grid[i][j] == 1) {
                        hasOne = true;
                        areaMinR = min(areaMinR, i);
                        areaMaxR = max(areaMaxR, i);
                        areaMinC = min(areaMinC, j);
                        areaMaxC = max(areaMaxC, j);
                    }
                }
            }
            return hasOne ? (areaMaxR - areaMinR + 1) * (areaMaxC - areaMinC + 1) : 0;
        };

        // 1 横向三分割（修正for循环语法和条件）
        for (int i = minR; i < maxR; i++) { 
            for (int j = i + 1; j < maxR; j++) {  // j与maxR比较（行）
                int a = getArea(minR, i, minC, maxC);       // 上
                int b = getArea(i + 1, j, minC, maxC);       // 中
                int c = getArea(j + 1, maxR, minC, maxC);    // 下
                if (a > 0 && b > 0 && c > 0) ans = min(ans, a + b + c);
            }
        }

        // 2 纵向三分割
        for (int i = minC; i < maxC; i++) {  
            for (int j = i + 1; j < maxC; j++) {  
                int a = getArea(minR, maxR, minC, i);       // 左
                int b = getArea(minR, maxR, i + 1, j);       // 中
                int c = getArea(minR, maxR, j + 1, maxC);    // 右
                if (a > 0 && b > 0 && c > 0) ans = min(ans, a + b + c);
            }
        }

        // 3 横向两部分 上面分成两部分
        for (int i = minR; i < maxR; i++) {
            int downArea = getArea(i + 1, maxR, minC, maxC);
            if (downArea == 0) continue;  // 下面为空则无效
            for (int j = minC; j < maxC; j++) {  
                int upLeft = getArea(minR, i, minC, j);
                int upRight = getArea(minR, i, j + 1, maxC);
                if (upLeft > 0 && upRight > 0) ans = min(ans, upLeft + upRight + downArea);
            }
        }

        // 4 横向两部分 下面分成两部分（修正内层for循环语法）
        for (int i = minR; i < maxR; i++) {
            int upArea = getArea(minR, i, minC, maxC);
            if (upArea == 0) continue;  // 上面为空则无效
            for (int j = minC; j < maxC; j++) {  
                int downLeft = getArea(i + 1, maxR, minC, j);
                int downRight = getArea(i + 1, maxR, j + 1, maxC);
                if (downLeft > 0 && downRight > 0) ans = min(ans, downLeft + downRight + upArea);
            }
        }

        // 5 纵向两部分 左边横向两部分（修正内层for循环语法和区域范围）
        for (int i = minC; i < maxC; i++) {
            int rightArea = getArea(minR, maxR, i + 1, maxC);
            if (rightArea == 0) continue;  // 右边为空则无效
            for (int j = minR; j < maxR; j++) {  
                int leftUp = getArea(minR, j, minC, i);  
                int leftDown = getArea(j + 1, maxR, minC, i);
                if (leftUp > 0 && leftDown > 0) ans = min(ans, leftUp + leftDown + rightArea);
            }
        }

        // 6 纵向两部分 右边横向两部分（修正内层for循环语法）
        for (int i = minC; i < maxC; i++) {
            int leftArea = getArea(minR, maxR, minC, i);
            if (leftArea == 0) continue;  // 左边为空则无效
            for (int j = minR; j < maxR; j++) {  
                int rightUp = getArea(minR, j, i + 1, maxC);
                int rightDown = getArea(j + 1, maxR, i + 1, maxC);
                if (rightUp > 0 && rightDown > 0) ans = min(ans, rightUp + rightDown + leftArea);
            }
        }

        return ans;
    }
};

// 法二
class Solution {
    // -------------------------- 辅助函数1：矩阵顺时针旋转90度 --------------------------
    // 作用：利用旋转对称性，将纵向分割问题转化为横向分割问题，复用solve函数，减少重复代码
    // 原理：原m行n列矩阵 → 旋转后n行m列，元素a[i][j] → 对应b[j][m-1-i]
    vector<vector<int>> rotate(const vector<vector<int>> a) {
        int m = a.size(), n = a[0].size();
        vector b(n, vector<int>(m)); // 旋转后矩阵维度：n行m列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                b[j][m - 1 - i] = a[i][j]; // 顺时针旋转90度的坐标映射公式
            }
        }
        return b;
    }

    // -------------------------- 辅助函数2：预处理子区域最小包含面积矩阵 --------------------------
    // 输入：二维数组a
    // 输出：f[i][j] → 代表a的「前i行（0~i-1行）、前j列（0~j-1列）」子区域中，包含所有1的最小矩形面积
    // 核心优化：通过border数组累积记录每列的边界信息，避免重复遍历子区域计算面积
    vector<vector<int>> minimumArea(const vector<vector<int>>& a) {
        int m = a.size(), n = a[0].size();
        vector f(m + 1, vector<int>(n + 1)); // f是(m+1)x(n+1)，索引从1开始对应实际行列
        // border[j]：存储到第j列（0~j-1列）为止的关键边界：
        // tuple<上边界行号, 左边界列号, 右边界列号>，pre_top=-1表示该列前无1
        vector<tuple<int, int, int>> border(n + 1, {-1, -1, -1});

        for (int i = 0; i < m; i++) { // 遍历每一行（对应f的i+1行）
            int left = -1, right = 0; // left：当前行最左1的列号，right：当前行最右1的列号
            for (int j = 0; j < n; j++) { // 遍历每一列（对应f的j+1列）
                if (a[i][j]) { // 当前位置是1，更新当前行的左右边界
                    if (left < 0) left = j; // 首次遇到1，记录左边界
                    right = j; // 持续更新右边界
                }

                // 解构border[j]的三个值：前j列的上边界、左边界、右边界
                auto& [pre_top, pre_left, pre_right] = border[j];
                if (left < 0) { // 当前行前j列无1，面积继承上一行（i行）的结果
                    f[i + 1][j + 1] = f[i][j + 1];
                } else if (pre_top < 0) { // 前j列首次出现1（当前行），面积为当前行的左右跨度
                    f[i + 1][j + 1] = right - left + 1;
                    border[j] = {i, left, right}; // 更新该列的边界为当前行信息
                } else { // 前j列已有1，合并历史边界与当前行边界，计算矩形面积
                    int l = min(pre_left, left); // 合并后左边界（取最小）
                    int r = max(pre_right, right); // 合并后右边界（取最大）
                    // 面积 = 左右跨度 × 上下跨度（当前行i - 历史上边界pre_top + 1）
                    f[i + 1][j + 1] = (r - l + 1) * (i - pre_top + 1);
                    border[j] = {pre_top, l, r}; // 更新该列的合并后边界
                }
            }
        }
        return f;
    }

    // -------------------------- 核心函数：计算单个方向矩阵的最小面积和 --------------------------
    // 输入：二维数组a（原矩阵或旋转后的矩阵）
    // 输出：该矩阵下满足条件的3个矩形面积和的最小值
    // 核心思路：通过预处理的面积矩阵，快速计算两种关键分割场景的面积和
    int solve(vector<vector<int>>& a) {
        int m = a.size(), n = a[0].size();
        
        // 预处理lr数组：lr[i] = {l, r}，l是第i行最左1的列号，r是第i行最右1的列号（l=-1表示该行无1）
        vector<pair<int, int>> lr(m);
        for (int i = 0; i < m; i++) {
            int l = -1, r = 0;
            for (int j = 0; j < n; j++) {
                if (a[i][j] > 0) {
                    if (l < 0) l = j;
                    r = j;
                }
            }
            lr[i] = {l, r};
        }

        // 生成4个方向的预处理面积矩阵（通过旋转复用minimumArea函数，避免重复编码）
        vector<vector<int>> lt = minimumArea(a); // lt：原方向（左上方向）的面积矩阵
        a = rotate(a);
        vector<vector<int>> lb = rotate(rotate(rotate(minimumArea(a)))); // lb：左下方向的面积矩阵（旋转3次回原方向）
        a = rotate(a);
        vector<vector<int>> rb = rotate(rotate(minimumArea(a))); // rb：右下方向的面积矩阵（旋转2次回原方向）
        a = rotate(a);
        vector<vector<int>> rt = rotate(minimumArea(a)); // rt：右上方向的面积矩阵（旋转1次回原方向）

        int ans = INT_MAX; // 初始化结果为最大值

        // 场景1：横向三分割（需至少3行，m>=3）
        // 分割为：上区域（0~i-1行） + 中区域（i~j-1行） + 下区域（j~m-1行）
        if (m >= 3) {
            for (int i = 1; i < m; i++) { // i是上区域与中区域的分割线（上区域共i行）
                int left = n, right = 0, top = m, bottom = 0; // 中区域的左右上下边界
                for (int j = i + 1; j < m; j++) { // j是中区域与下区域的分割线（下区域从j行开始）
                    // 取中区域第j-1行的lr信息（j-1是中区域的当前行）
                    auto& [l, r] = lr[j - 1];
                    if (l >= 0) { // 该行列有1，更新中区域的边界
                        left = min(left, l);
                        right = max(right, r);
                        top = min(top, j - 1);
                        bottom = j - 1;
                    }
                    // 计算面积和：上区域面积（lt[i][n]：前i行全列） + 中区域面积 + 下区域面积（lb[j][n]：从j行开始全列）
                    ans = min(ans, lt[i][n] + (right - left + 1) * (bottom - top + 1) + lb[j][n]);
                }
            }
        }

        // 场景2：先横后纵分割（需至少2行2列，m>=2且n>=2）
        // 两种子场景：
        // 子场景1：上区域全列（lt[i][n]） + 下区域左半（lb[i][j]） + 下区域右半（rb[i][j]）
        // 子场景2：上区域左半（lt[i][j]） + 上区域右半（rt[i][j]） + 下区域全列（lb[i][n]）
        if (m >= 2 && n >= 2) {
            for (int i = 1; i < m; i++) { // i是横向分割线（上区域i行，下区域m-i行）
                for (int j = 1; j < n; j++) { // j是纵向分割线（左半j列，右半n-j列）
                    ans = min(ans, lt[i][n] + lb[i][j] + rb[i][j]); // 子场景1
                    ans = min(ans, lt[i][j] + rt[i][j] + lb[i][n]); // 子场景2
                }
            }
        }

        return ans;
    }

public:
    // -------------------------- 主函数 --------------------------
    // 核心逻辑：利用旋转对称性，计算原矩阵和旋转后矩阵的最小面积和，取较小值
    // 原因：原矩阵的纵向分割场景 ≡ 旋转后矩阵的横向分割场景，复用solve避免重复处理
    int minimumSum(vector<vector<int>>& grid) {
        auto a = rotate(grid); // 生成旋转90度的矩阵
        // 取原矩阵的解和旋转矩阵的解的最小值，覆盖所有分割场景
        return min(solve(grid), solve(a));
    }
};